In a packet data communications network (Internet, Ethernet, token ring, and the like) address translation is an integral component of the system. In particular, there is a requirement of doing source and destination address lookups.
Using the Internet as a basis for discussion, three main factors contribute to the speed of traffic over the Internet: link speeds, router data throughput, and packet forwarding rates. Readily available solutions exist for the first two factors. For example, fiber-optics can provide faster links and switching technology can be used to move packets through a router at gigabit speeds. The present invention deals with the third factor, packet forwarding. The main step in packet forwarding is to lookup the destination address of an incoming packet in a routing database. Internet routers search a database for the longest prefix matching a destination IP address. Traditional techniques for exact matching, such as perfect hashing, binary search, and standard content addressable memories (CAM) cannot directly be used for effective Internet address lookups. In particular, perfect hashing and binary search can be used for IP lookups, but typically require several microseconds per lookup; and CAM based solutions are considered to be expensive since multiple CAMs operating in parallel need to be used (i.e. one CAM for each prefix bin).
A forwarding database in an IP router consists of a number of variable length network addresses. The length of the network address is given by a prefix value. When an IP router receives a packet, it must compute which of the network addresses in its database has the longest match when compared to the destination address in the packet. The packet is then forwarded to the output link associated with that prefix. For example, a forwarding database may have the following network addresses (NA): NA1=0101, NA2=0101101 and NA3=010110101011. In this example the destination address is 16-bits long, the corresponding prefix values defines the network portion of the destination address: P1=1111000000000000, P2=1111111000000000 and P3=1111111111110000. An address whose first 12 bits are 010101101011 has longest matching prefix P1. An address whose first 12 bits are 010110101101 has longest matching prefix P3.
To solve the longest matching prefix problem, a routing table can be implemented using a large memory array to provide a 32-bit binary decoding tree. With a tree depth of 32, a unique decode is available for each possible IP address. Since the network portion of the address is less than 32 bits, the decoding of the network address is internal to the memory decoding structure, consequently an internal decode level defined by a network address results in a range of decoded 32-bit addresses that may be associated with the given network address.
From a routing perspective, each network address internal to the memory defines a range of IP addresses that are routed in the same manner. With a plurality of network addresses being located internal to the memory, there will be instances in which two or more network addresses share the same IP address, the network address selected will be the one that is lowest down the decoding chain.
A decoding tree with a depth of 32 results in 4,300 million IP addresses and requires an excessively large memory that uses only one memory access. Since the number of network addresses used by a router located within the backbone of the Internet typically requires 40,000 entries, the routing table can be reduced to a compact forwarding table using significantly less memory. Existing solutions such as (1) algorithms for best matching prefix using binary search on hash tables organized by prefix lengths (described in Scalable High Speed IP Routing Lookups, Waldvogel et al., http://www.tik.ee.ethz.ch/tik/research/Research.html) and (2) using a forwarding table data structure designed for quick routing lookups (described in Small Forwarding Tables for Fast Routing Lookups, Degermark et al., http://www.cdt.luth.se/net/publications.html) typically increase the number of memory accesses to reduce the physical size of the data structure while increasing the functional complexity for forwarding lookups. This functional complexity directly affects the ability to provide a simple method of inserting or deleting connection entries from the forwarding solutions.